#include <vector>
#include <math.h>
#include <bitset>
#include <iostream>
using namespace std;

namespace zty{
  template <size_t N>
  class bitset{
    vector<char> _bt;
    size_t _count;
    
  public:
    bitset()
      :_bt(ceil((double)N/8), 0),
      _count(0)
    {}

    void set(size_t x){
      if(x>N) return;
      size_t i = x/8;
      size_t j = x%8;
      _bt[i] |= (1<<j);
      ++_count;
    }

    void reset(size_t x)
    {
      if(x>N) return;
      size_t i = x/8;
      size_t j = x%8;
      _bt[i] &= ~(1<<j);
      --_count;
    }

    bool test(size_t x)
    {
      if(x>N) return false;
      size_t i = x/8;
      size_t j = x%8;
      return _bt[i] & (1<<j);
    }

    size_t count(){
      return _count;
    }

    size_t size(){
      return N;
    }
  };

  template <size_t N>
  class twobitset1{
    bitset<N> bs1;
    bitset<N> bs2;
  public:
    void set(size_t x){
      if(!bs1.test(x) && !bs2.test(x))
      {
        bs2.set(x);
      }
      else if(!bs1.test(x) && bs2.test(x))
      {
        bs1.set(x);
        bs2.reset(x);
      }
    }
    void print_once_num(){
      for(size_t i = 0; i<N; ++i)
      {
        if(!bs1.test(i) && bs2.test(i))
        {
          cout << i << " ";
        }
      }
      cout << endl;
    }
  };

  template <size_t N>
    class twobitset2{
      bitset<N> bs1;
      bitset<N> bs2;
    public:
      void setbs1(size_t x){
        bs1.set(x);
      } 
      void setbs2(size_t x){
        bs2.set(x);
      } 
      void print_intersection_set(){
        for(size_t i = 0; i<N; ++i)
        {
          if(bs1.test(i) && bs2.test(i))
          {
            cout << i << " ";
          }
        }
        cout << endl;
      }
    };

  template <size_t N>
  class twobitset3{
    bitset<N> bs1;
    bitset<N> bs2;
  public:
    void set(size_t x){
      if(!bs1.test(x) && !bs2.test(x))
      {
        bs2.set(x);
      }
      else if(!bs1.test(x) && bs2.test(x))
      {
        bs1.set(x);
        bs2.reset(x);
      }
      else if(bs1.test(x) && !bs2.test(x))
      {
        bs2.set(x);
      }
    }
    void print_atmost_twice(){
      for(size_t i = 0; i<N; ++i)
      {
        if(!bs1.test(i) && bs2.test(i))
        {
          cout << i << " ";
        }
        else if(bs1.test(i) && !bs2.test(i))
        {
          cout << i << " ";
        }
      }
      cout << endl;
    }
  };
  
  struct BKDRHash
  {
    size_t operator()(const string& s)
    {
      // BKDR
      size_t value = 0;
      for (auto ch : s)
      {
        value += ch;
        value *= 31;
      }
      return value;
    }
  };

  struct APHash
  {
    size_t operator()(const string& s)
    {
      size_t hash = 0;
      for (size_t i = 0; i < s.size(); i++)
      {
        if ((i & 1) == 0)
        {
          hash ^= ((hash << 7) ^ s[i] ^ (hash >> 3));
        }
        else
        {
          hash ^= (~((hash << 11) ^ s[i] ^ (hash >> 5)));
        }
      }
      return hash;
    }
  };

  struct DJBHash
  {
    size_t operator()(const string& s)
    {
      size_t hash = 5381;
      for (auto ch : s)
      {
        hash += (hash << 5) + ch;
      }
      return hash;
    }
  };

    template <size_t N, class K = string,
      class Hash1 = BKDRHash,
      class Hash2 = APHash,
      class Hash3 = DJBHash>
    class BloomFilter{
      std::bitset<N*100> _bs;

    public:
      void set(const K& key){
        size_t hashi1 = Hash1()(key) % _bs.size();
        _bs.set(hashi1);
        size_t hashi2 = Hash2()(key) % _bs.size();
        _bs.set(hashi2);
        size_t hashi3 = Hash3()(key) % _bs.size();
        _bs.set(hashi3);
      }

      bool test(const K& key){
        size_t hashi1 = Hash1()(key) % _bs.size();
        if(!_bs.test(hashi1)) return false; //准确的
        size_t hashi2 = Hash2()(key) % _bs.size();
        if(!_bs.test(hashi2)) return false; //准确的
        size_t hashi3 = Hash3()(key) % _bs.size();
        if(!_bs.test(hashi3)) return false; //准确的
        return true; //可能存在误判
      }
    };
}
